#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DEBUG
//Sparse Matrix


#define ROW_MAX 20
#define COL_MAX 20
#define SMAX (ROW_MAX * COL_MAX)

//triple table
//定义三元组类型
struct triple_node {
	//储存非零元素的行和列信息, 1-based
	unsigned int row;
	unsigned int col;  
	int val; //非零元素的值    
};      

struct SPMatrix {
	//矩阵的行、列和非零元素的个数  
	unsigned int rows;
	unsigned int cols;
	unsigned int nums;
	struct triple_node data[SMAX]; //三元组表  
};

//0029 test data
struct SPMatrix input_matrix = {
	4,4,3,
	{
		{1,1,1},
		{2,1,2},
		{3,2,3}
	}
};

//0030 test data
struct SPMatrix input_matrix30_1 = {
	3,4,3,
	{
		{1,1,1},
		{1,3,1},
		{2,2,2}
	}
};

struct SPMatrix input_matrix30_2 = {
	3,4,2,
	{
		{1,2,1},
		{2,2,3},
	}
};

//0032 test data
struct SPMatrix input_matrix32_1 = {
	3,3,4,
	{
		{1,1,1},
		{2,2,2},
		{2,3,4},
		{3,1,-4}
	}
};

struct SPMatrix input_matrix32_2 = {
	3,3,4,
	{
		{1,3,-2},
		{2,3,-5},
		{3,1,8},
		{3,2,-6}
	}
};


//三元组表
void print_matrix_triple(char* str, struct SPMatrix* pmatrix)
{
	unsigned int i;
	printf("\n");
	if (str)
		printf("%s\n", str);

	for (i = 0; i < pmatrix->nums; i++) {
		printf("%d %d %d\n", pmatrix->data[i].row,
			pmatrix->data[i].col, pmatrix->data[i].val);
	}
	printf("\n");
}

void print_matrix_origin(char* str, struct SPMatrix* pmatrix)
{
	unsigned int i, j, k;
	int val;
	if (str)
		printf("%s\n", str);

	for (i = 0, k = 0; i < pmatrix->rows; i++) {
		for (j = 0; j < pmatrix->cols; j++) {
			val = 0;
			if (((i + 1) == pmatrix->data[k].row) &&
				((j + 1) == pmatrix->data[k].col)) {
				val = pmatrix->data[k].val;
				k++;
			}
			printf("%d ", val);
		} //end 2nd for loop
		printf("\n");
	} //end 1st for loop

	printf("\n");
}

//matrix transpose, 0029
void transpose(struct SPMatrix* pmatrix)
{
	unsigned int col, num, index;
	struct SPMatrix* result_spm;

	if (!pmatrix->nums) //NULL
		return;

	result_spm = malloc(sizeof(struct SPMatrix));
	memset(result_spm, 0, sizeof(struct SPMatrix));
	result_spm->cols = pmatrix->rows;
	result_spm->rows = pmatrix->cols;
	result_spm->nums = pmatrix->nums;

	for (col = 1, index = 0; col <= pmatrix->cols; col++) {
		for (num = 0; num < pmatrix->nums; num++) {
			if (pmatrix->data[num].col == col) {
				result_spm->data[index].col = pmatrix->data[num].row;
				result_spm->data[index].row = pmatrix->data[num].col;
				result_spm->data[index].val = pmatrix->data[num].val;
				index++;
			}
		}
	}

#ifdef DEBUG
	print_matrix_origin("after transpose", result_spm);
	print_matrix_triple("after transpose", result_spm);
#else
	print_matrix_triple(NULL, result_spm);
#endif
	free(result_spm);
}

void get_userinput29(struct SPMatrix* spm)
{
	struct triple_node node;
	unsigned int rows;

	memset(spm, 0, sizeof(struct SPMatrix));
	//4, 4
	scanf("%d", &spm->rows);
	scanf("%d", &spm->cols);

	rows = 0;
	while (1) {
		scanf("%d", &node.row);
		scanf("%d", &node.col);
		scanf("%d", &node.val);
		if (!node.row && !node.col && !node.val)
			break;
		memcpy(&spm->data[rows], &node, sizeof(struct triple_node));
		rows++;
	}
	spm->nums = rows;
}

void cs_0029(void)
{
	printf("start 9000000029 test\n");
#ifdef DEBUG
	print_matrix_triple("origin triple", &input_matrix);
	print_matrix_origin("origin matrix:", &input_matrix);
#else
	get_userinput29(&input_matrix);
#endif
	//print_matrix_triple("origin triple", &input_matrix);
	transpose(&input_matrix); 
}


//将指定位置的元素值赋给变量
int matrix_lookup(struct SPMatrix* t, unsigned int row, unsigned int col)
{
	unsigned int k;
	int val = 0;

	for (k = 0; k < t->nums; k++) {
		if (t->data[k].row == row && t->data[k].col == col) {
			//found it
			val = t->data[k].val;
			break;
		}
	}

	return val;
}

//cs0030, c = a + b
void matrix_add(struct SPMatrix* a, struct SPMatrix* b)
{
	struct SPMatrix* c;
	unsigned int row, col;
	int value;
	int va, vb;
	unsigned int nums;

	if ((a->cols != b->cols) || (a->rows != b->rows))
		return;

	c = malloc(sizeof(struct SPMatrix));
	memset(c, 0, sizeof(struct SPMatrix));
	c->cols = a->cols;
	c->rows = a->rows;

	//add
	for (row = 1, nums = 0; row <= c->rows; row++) {
		for (col = 1; col <= c->cols; col++) {
			va = matrix_lookup(a, row, col);
			vb = matrix_lookup(b, row, col);
			value = va + vb;
			if (value) {
				c->data[nums].row = row;
				c->data[nums].col = col;
				c->data[nums].val = value;
				nums++;
			}
		}
	}
	c->nums = nums;
	//add end
#ifdef DEBUG
	print_matrix_origin("after add", c);
	print_matrix_triple("after add", c);
#else
	print_matrix_triple(NULL, c);
#endif
	free(c);
}

void get_userinput_30_extra(struct SPMatrix *a, unsigned int m, unsigned int n,
		unsigned int nums)
{
	unsigned int i;
	struct triple_node node;

	for (i = 0; i < nums; i++) {
		scanf("%d", &node.row);
		scanf("%d", &node.col);
		scanf("%d", &node.val);
		memcpy(&a->data[i], &node, sizeof(struct triple_node));
	}
	a->rows = m;
	a->cols = n;
	a->nums = nums;
}

void get_userinput30(struct SPMatrix *a, struct SPMatrix *b)
{
	unsigned int m, n, t1, t2;

	//3 4 3 2
	scanf("%d", &m);
	scanf("%d", &n);
	scanf("%d", &t1);
	scanf("%d", &t2);

	get_userinput_30_extra(a, m, n, t1);
	get_userinput_30_extra(b, m, n, t2);
}


void get_userinput32(struct SPMatrix* a, struct SPMatrix* b)
{
	get_userinput29(a);
	get_userinput29(b);
}



void cs_0030(void)
{
	printf("start 9000000030 test\n");
#ifdef DEBUG
	print_matrix_triple("origin triple1", &input_matrix30_1);
	print_matrix_origin("origin matrix1:", &input_matrix30_1);
	print_matrix_triple("origin triple2", &input_matrix30_2);
	print_matrix_origin("origin matrix2:", &input_matrix30_2);
#else
	get_userinput30(&input_matrix30_1, &input_matrix30_2);
#endif
	matrix_add(&input_matrix30_1, &input_matrix30_2);
}


//cs0030, c = a * b
void matrix_multi(struct SPMatrix* a, struct SPMatrix* b)
{
	struct SPMatrix* c;
	unsigned int nums = 0;
	unsigned int row, col, k;
	int value;
	int va, vb;

	if(a->cols != b->rows) {
		printf("a col is %d, b row is %d \n",a->cols, b->rows);
		return;
	}

	c = malloc(sizeof(struct SPMatrix));
	memset(c, 0, sizeof(struct SPMatrix));
	c->rows = a->rows;
	c->cols = b->cols;

	//multi start: C = A * B
	//A: m*s , B: s*n, C = A*B = m rows, n cols
	//Cij = Aik * Bkj, k: from 1 to s(cols of A)
	for (row = 1, nums = 0; row <= c->rows; row++) {
		for (col = 1; col <= c->cols; col++) {
			value = 0;
			for (k = 1; k <= c->cols; k++) {
				va = matrix_lookup(a, row, k);
				vb = matrix_lookup(b, k, col);
				value = value + va * vb;
			}
			if (value) {
				c->data[nums].row = row;
				c->data[nums].col = col;
				c->data[nums].val = value;
				nums++;
			}
		}
	}
	c->nums = nums;
	//multi end
#ifdef DEBUG
	print_matrix_origin("after multi", c);
	print_matrix_triple("after multi", c);
#else
	print_matrix_triple(NULL, c);
#endif
	free(c);
}

void cs_0032(void)
{
	printf("start 9000000032 test\n");
#ifdef DEBUG
	print_matrix_triple("origin triple1", &input_matrix32_1);
	print_matrix_origin("origin matrix1:", &input_matrix32_1);
	print_matrix_triple("origin triple2", &input_matrix32_2);
	print_matrix_origin("origin matrix2:", &input_matrix32_2);
#else
	get_userinput32(&input_matrix32_1, &input_matrix32_2);
#endif
	matrix_multi(&input_matrix32_1, &input_matrix32_2);
}

/* Orthogonal List, OL */
/*十字链表的结构类型定义如下：*/
typedef struct OLNode
{
	struct triple_node data; /*非零元素*/
    struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
    struct OLNode *down;
} OLNode, *OLink;

/*
	row_head[0]: list head, no real data
	col_head[0]: list head, no real data
*/
typedef struct
{
	/*行、列链表的头指针向量*/
	OLNode row_head[ROW_MAX]; //rhead, save one row data, only care ->right
	OLNode col_head[COL_MAX]; //chead, save one column data, only care ->down
    unsigned int rows, cols, nums; /*稀疏矩阵的行数、列数、非零元素的个数*/
} CrossList;

//head: list head
void insert_to_row_list(OLink head, OLink newNode)
{
	OLink pos, pre;

	//find right position
	pre = head; //pre point to head
	pos = pre->right; //skip head node
	while (pos) {
		if (newNode->data.col <= pos->data.col) {
			//found, pre -> pos changed to pre -> newNode -> pos
			pre->right = newNode;
			newNode->right = pos;
			break;
		}
		pre = pos;
		pos = pos->right;
	} //end while
	//reach to list tail, add to tail
	pre->right = newNode;
}

void insert_to_col_list(OLink head, OLink newNode)
{
	OLink pos, pre;

	//insert to col list
	//find right position
	pre = head; //pre point to head
	pos = pre->down; //skip head node
	while (pos) {
		if (newNode->data.row <= pos->data.row) {
			//found, pre -> pos changed to pre -> newNode -> pos
			pre->down = newNode;
			newNode->down = pos;
			break;
		}
		pre = pos;
		pos = pos->down;
	} //end while
	//reach to list tail, add to tail
	pre->down = newNode;
}

//insert one node to OL list
//insert "node" to "list"
void insert_OLlist(CrossList *list, struct triple_node *node)
{
	OLink newNode;

	if (!list || !node)
		return;
	newNode = malloc(sizeof(OLNode));
	newNode->right = NULL;
	newNode->down = NULL;
	memcpy(&newNode->data, node, sizeof(struct triple_node));

	if (!list->nums) { //null list
		list->row_head[node->row].right = newNode;
		list->col_head[node->col].down = newNode;
		list->nums++;
	} else {//not null
		insert_to_row_list(&list->row_head[node->row], newNode);
		insert_to_col_list(&list->col_head[node->col], newNode);
	}
}

void print_OLlist_triple(char* str, CrossList* list)
{
	unsigned int i;
	OLink pos;
	
	printf("\n");
	if (str)
		printf("%s\n", str);
	//tranverse list by row
	for (i = 1; i <= list->rows; i++) {
		pos = &list->row_head[i]; //point to head
		pos = pos->right; //skip head node
		while (pos) {
			printf("%d %d %d\n", pos->data.row, pos->data.col, pos->data.val);
			pos = pos->right;
		}
	}
	printf("\n");
}

void print_OLlist_origin(char* str, CrossList* list)
{
	unsigned int row, col;
	OLink pos;

	if (str)
		printf("%s\n", str);

	for (row = 1; row <= list->rows; row++) {
		pos = &list->row_head[row]; //point to head
		pos = pos->right; //skip head node
		for (col = 1; col <= list->cols; col++) {
			if (pos && row == pos->data.row && col == pos->data.col) {
				printf("%d ", pos->data.val);
				pos = pos->right;
			} else {
				printf("0 ");
			}
		}
		printf("\n");
	}
}

CrossList* build_OLlist(struct SPMatrix* matrix)
{
	CrossList* list;
	unsigned int nums;

	list = malloc(sizeof(CrossList));
	memset(list, 0, sizeof(CrossList));
	if (!matrix) //only malloc space
		return list;

	list->cols = matrix->cols;
	list->rows = matrix->rows;
	for (nums = 0; nums < matrix->nums; nums++) {
		insert_OLlist(list, &matrix->data[nums]);
	}

	return list;
}

//free resources
void destroy_OLlist(CrossList* list)
{
	OLink pos, next;
	unsigned int row;

	for(row = 1; row <= list->rows; row++) {
		pos = &list->row_head[row]; //point to head
		pos = pos->right; //skip head
		while (pos) {
			next = pos->right;
			free(pos);
			pos = next;
		}
	}
	free(list);
}

//find node according row/col pair
int list_lookup(CrossList* list, unsigned int row, unsigned int col)
{
	int val = 0;
	OLink pos;

	if (row > list->rows || col > list->cols)
		return 0;

	pos = &list->row_head[row]; //pre point to head
	pos = pos->right; //skip head
	while (pos) {
		if (pos->data.col == col) {
			//found
			val = pos->data.val;
			break;
		}
		pos = pos->right;
	}

	return val;
}

//cs0031, c = a + b, Orthogonal List version
void matrix_add_OLlist(struct SPMatrix* a, struct SPMatrix* b)
{
	CrossList *lista, *listb, *listc;
	unsigned int row, col;
	int value;
	int va, vb;
	unsigned int nums;
	struct triple_node node;

	if ((a->cols != b->cols) || (a->rows != b->rows))
		return;
	
	lista = build_OLlist(a);
	listb = build_OLlist(b);
	listc = build_OLlist(NULL);
	listc->cols = a->cols;
	listc->rows = a->rows;

	//listc = lista + listb
	//add
	for (row = 1, nums = 0; row <= listc->rows; row++) {
		for (col = 1; col <= listc->cols; col++) {
			va = list_lookup(lista, row, col);
			vb = list_lookup(listb, row, col);
			value = va + vb;
			if (value) {
				node.row = row;
				node.col = col;
				node.val = value;
				insert_OLlist(listc, &node);
				nums++;
			}
		}
	}
	listc->nums = nums;
	//add end

#ifdef DEBUG
	print_OLlist_origin("lista origin", lista);
	print_OLlist_triple("lista triple", lista);
	print_OLlist_origin("listb origin", listb);
	print_OLlist_triple("listb triple", listb);

	print_OLlist_origin("after add", listc);
	print_OLlist_triple("after add", listc);
#else
	print_OLlist_triple(NULL, listc);
#endif
	destroy_OLlist(lista);
	destroy_OLlist(listb);
	destroy_OLlist(listc);
}

/* cs0030 and cs0031: input and output are same, 
	only data structure is not same 
	cs0030: array
	cs0031: Orthogonal List
*/
void cs_0031(void)
{
	printf("start 9000000031 test\n");
#ifdef DEBUG
	print_matrix_triple("origin triple1", &input_matrix30_1);
	print_matrix_origin("origin matrix1:", &input_matrix30_1);
	print_matrix_triple("origin triple2", &input_matrix30_2);
	print_matrix_origin("origin matrix2:", &input_matrix30_2);
#else
	get_userinput30(&input_matrix30_1, &input_matrix30_2);
#endif
	matrix_add_OLlist(&input_matrix30_1, &input_matrix30_2);
}

/*
 * 0029 test:
input:
 4 4
 1 1 1
 2 1 2
 3 2 3
 0 0 0
output:
 1 1 1
 1 2 2
 2 3 3

 0030 test:
input:
	3 4 3 2
	1 1 1
	1 3 1
	2 2 2
	1 2 1
	2 2 3

output:
	1 1 1
	1 2 1
	1 3 1
	2 2 5

 0031 test: same as 0030
 0032 test:
input:
	3 3
	1 1 1
	2 2 2
	2 3 4
	3 1 -4
	0 0 0
	3 3
	1 3 -2
	2 3 -5
	3 1 8
	3 2 -6
	0 0 0

output:
	1 3 -2
	2 1 32
	2 2 -24
	2 3 -10
	3 3 8


 * */
int main(int argc, char **argv)
{
	cs_0029();
	cs_0030();
	cs_0031();
	cs_0032();
	return 0;
}
